The present inventive concept is directed to a Montgomery multiplier and a Montgomery multiplication method.
Modular operations provide the underpinning for some of the most widely used public key cryptographic algorithms, such as RSA (Rivest Shamir Adelman) and ECC (elliptic curve cryptography). The basic modular operations include modular addition/subtraction and modular multiplication. Modular division is not used in most algorithms because of its high computational complexity. If necessary, a modular division can be performed using modular multiplication. Modular multiplication can be performed by a set of modular additions. In this case, modular multiplication corresponds to a serialized multiplication and its computation speed is very low. Thus, to improve its performance, modular multiplication is generally performed in the form of a digit-serialized multiplication by increasing a radix.
The operations typically performed by a public key operator include modular addition/subtraction and a modular multiplication. Since modular multiplication is more complicated and has a longer critical path than modular addition/subtraction, the maximum operating frequency of an overall security operator may depend on how modular multiplication is implemented and used.
Modular multiplication includes two operations: a multiplication and a reduction. A modular multiplication algorithm that is widely used in hardware design is the Montgomery multiplication algorithm. The Montgomery multiplication algorithm can effectively perform a reduction operation.